import java.util.Arrays;

/**
 * 260. 只出现一次的数字 III
 * https://leetcode-cn.com/problems/single-number-iii/
 */
public class Solutions_260 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 3, 2, 5};  // output: {3, 5} or {5, 3}
//        int[] nums = {4, 1, 4, 6};  // output: {1, 6} or {6, 1}
//        int[] nums = {1, 2, 10, 4, 1, 4, 3, 3};  // output: {2, 10} or {10, 2}

        int[] result = singleNumber(nums);
        System.out.println(Arrays.toString(result));
    }

    public static int[] singleNumber(int[] nums) {
        int twoNumXor = 0;
        for (int num : nums) {
            twoNumXor = twoNumXor ^ num;
        }
        // 取 lowNumXor 最低位的 1
        /**
         * 通过计算得到 twoNumXor 二进制上最低位的 1：one
         * 可将 nums 中全部元素分成 2 组，即 (num & one) == 0 的和不等于 0 的
         * 例如 数组中只出现一次的数：10(0b1010) 与 2(0b0010),得到异或结果 8(0b1000)
         *       1010   10                            0001
         *    ^  0010    2                         ^  0110
         *    ---------                           -----------
         *       1000(最低位上的 1 就是 1000)            0111（最低位上的 1 就是 0001）
         */
        int lowOneBit = twoNumXor & (-twoNumXor);
        int res = 0;

        for (int num : nums) {
            // num & lowOneBit 等于 0 的为一组，不等于 0 的为一组，两个只出现一次的元素
            // 则是在不同的组内
            if ((num & lowOneBit) != 0) {
                res ^= num;
            }
        }
        return new int[]{res, twoNumXor ^ res};
    }
}
